package A;

import java.util.HashMap;
import java.util.Map;

class Node{
    Node pre;
    Node next;
    int key;
    int value;
    public Node(int key,int value){
        this.key=key;
        this.value=value;
    }
}


public  class LRU {
    public static void main(String[] args) {
        LRU l=new LRU(3);
        l.put(1,1);
        l.put(2,2);
        l.put(3,3);
        System.out.println(l.get(1));
        l.put(4,4);
        System.out.println(l.get(1));

    }


    private int capacity;
    private int size;
    Node head=null;
    Node tail=null;
    Map<Integer,Node> map=new HashMap<>();
    public LRU(int capacity){
        this.capacity=capacity;
        size=0;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next=tail;
        tail.pre=head;
    }
    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        Node res=map.get(key);
        moveToHead(res);
        return res.value;
    }
    public void put(int key,int value){

        Node node=new Node(key,value);

        if(map.containsKey(key)){
            Node temp=map.get(key);
            removeNode(temp);
            size--;
        }else{
            if(size==capacity){
                int delkey=removeTail().key;
                map.remove(delkey);
                size--;
            }
        }
        map.put(key,node);
        addFirst(node);
        size++;
    }
    public void addFirst(Node node){
        node.next=head.next;
        head.next.pre=node;
        head.next=node;
        node.pre=head;
    }
    public Node removeTail(){
        Node res=tail.pre;
        removeNode(res);
        return res;
    }
    public void removeNode(Node node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
        node.next=null;
        node.pre=null;
    }
    public void moveToHead(Node node){
        removeNode(node);
        addFirst(node);
    }

}

//class DList{
//    Node head=null;
//    Node tail=null;
//    public DList() {
//         head = new Node(0, 0);
//         tail = new Node(0, 0);
//         head.next=tail;
//         tail.pre=head;
//    }
//    public void addFirst(Node node){
//        node.next=head.next;
//        head.next.pre=node;
//        head.next=node;
//        node.pre=head;
//    }
//    public Node removeTail(){
//        Node res=tail.pre;
//        removeNode(res);
//        return res;
//    }
//    public void removeNode(Node node){
//        node.pre.next=node.next;
//        node.next.pre=node.pre;
//        node.next=null;
//        node.pre=null;
//    }
//    public void moveToHead(Node node){
//        removeNode(node);
//        addFirst(node);
//    }
//}